package com.atguigu.Recursion;

/**
 * description:8皇后问题
 * Created by 才睡醒 on 2021-06-11
 */
public class Queue8 {
    //定义一个max表示有多少皇后
    int max = 8;
    int[] array = new int[max];
    private int count = 0;
    public static void main(String[] args) {
        Queue8 queue8 = new Queue8();
        queue8.check(0);
        System.out.println(queue8.count);
       // queue8.print();


    }

    //编写一个方法，放置第n个皇后
    public void check(int n) {
        if (n == max) {  //如果n等于8时候，证明已经放置了8个皇后
            print();
            return;
        }
        for (int i = 0; i < max; i++) {
            array[n] = i;   //先把当前的这个皇后n，放到改行第一列
            if(judge(n)){//如果检查通过，进入递归
                check(n+1);
            }
            //如果冲突,继续执行array[n] = i;
        }
    }


    //查看当我们放置第n个皇后, 就去检测该皇后是否和前面已经摆放的皇后冲突
    public boolean judge(int n) {
        //遍历已经摆放的皇后和前面的皇后的个数

        for (int i = 0; i < n; i++) {
            //判断两个二皇后是否在同一列 || 两个皇后是否在同一斜线
            if (array[i] == array[n] || Math.abs(n - i) == Math.abs(array[n] - array[i])) { //array[i]==array[n]相等表示新加入的皇后和已经存在的皇后在同一列
                // Math.abs(n-i) == Math.abs(array[n] - array[i])
                //由于结果是一维数组    arr = {0 , 4, 7, 5, 2, 6, 1, 3}
                //arr[i] 等于 val
                //arr的下标i+1表示几行，值val+1表示第几列
                //Math.abs(n-i) 得出 行的差值， Math.abs(array[n] - array[i])得出列的差值。如果行差和列差一样证明是在同一斜线上
                return false;
            }
        }
        return true;
    }

    private void print(){
        count++;
        for (int i = 0; i <array.length ; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }

}

